{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #自行车炫技赛场"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #memoization #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #记忆化搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bicycleYard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #自行车炫技赛场"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "「力扣挑战赛」中 `N*M` 大小的自行车炫技赛场的场地由一片连绵起伏的上下坡组成，场地的高度值记录于二维数组 `terrain` 中，场地的减速值记录于二维数组 `obstacle` 中。\n",
    "- 若选手骑着自行车从高度为 `h1` 且减速值为 `o1` 的位置到高度为 `h2` 且减速值为 `o2` 的相邻位置（上下左右四个方向），速度变化值为 `h1-h2-o2`（负值减速，正值增速）。\n",
    "\n",
    "选手初始位于坐标 `position` 处且初始速度为 1，请问选手可以刚好到其他哪些位置时速度依旧为 1。请以二维数组形式返回这些位置。若有多个位置则按行坐标升序排列，若有多个位置行坐标相同则按列坐标升序排列。\n",
    "\n",
    "**注意：** 骑行过程中速度不能为零或负值\n",
    "\n",
    "**示例 1：**\n",
    "> 输入\b：`position = [0,0], terrain = [[0,0],[0,0]], obstacle = [[0,0],[0,0]]`\n",
    "> \n",
    "> 输出：`[[0,1],[1,0],[1,1]]`\n",
    "> \n",
    "> 解释：\n",
    "> 由于当前场地属于平地，根据上面的规则，选手从`[0,0]`的位置出发都能刚好在其他处的位置速度为 1。\n",
    "\n",
    "**示例 2：**\n",
    "> 输入\b：`position = [1,1], terrain = [[5,0],[0,6]], obstacle = [[0,6],[7,0]]`\n",
    "> \n",
    "> 输出：`[[0,1]]`\n",
    "> \n",
    "> 解释：\n",
    "> 选手从 `[1,1]` 处的位置出发，到 `[0,1]` 处的位置时恰好速度为 1。\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `n == terrain.length == obstacle.length`\n",
    "- `m == terrain[i].length == obstacle[i].length`\n",
    "- `1 <= n <= 100`\n",
    "- `1 <= m <= 100`\n",
    "- `0 <= terrain[i][j], obstacle[i][j] <= 100`\n",
    "- `position.length == 2`\n",
    "- `0 <= position[0] < n`\n",
    "- `0 <= position[1] < m`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kplEvH](https://leetcode.cn/problems/kplEvH/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kplEvH](https://leetcode.cn/problems/kplEvH/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,0]\\n[[0,0],[0,0]]\\n[[0,0],[0,0]]', '[1,1]\\n[[5,0],[0,6]]\\n[[0,6],[7,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(terrain), len(terrain[0])\n",
    "        vis = set()\n",
    "        q = deque()\n",
    "        q.append((position[0], position[1], 1))\n",
    "        vis.add((position[0], position[1], 1))\n",
    "        ans = []\n",
    "        while q:\n",
    "            x, y, s = q.popleft()\n",
    "            if s == 1:\n",
    "                ans.append([x, y])\n",
    "            direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "            for dx, dy in direction:\n",
    "                xx, yy = x + dx, y + dy\n",
    "                if m > xx >= 0 and 0 <= yy < n and s + terrain[x][y] - terrain[xx][yy] - obstacle[xx][yy] > 0:\n",
    "                    ss = s + terrain[x][y] - terrain[xx][yy] - obstacle[xx][yy]\n",
    "                    if (xx, yy, ss) not in vis:\n",
    "                        vis.add((xx, yy, ss))\n",
    "                        q.append((xx, yy, ss))\n",
    "\n",
    "        return sorted(ans[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n,m=len(terrain),len(terrain[0])\n",
    "        vis=set()\n",
    "        q=deque()\n",
    "        # 状态DFS需要带上状态,即速度\n",
    "        q.appendleft((position[0],position[1],1))\n",
    "        vis.add((position[0],position[1],1))\n",
    "        ans=[]\n",
    "        while q:\n",
    "            x,y,s=q.pop()\n",
    "            if s==1:\n",
    "                ans.append(list((x,y)))\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if n>xx>=0<=yy<m and s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]>0:\n",
    "                    ss=s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]\n",
    "                    if (xx,yy,ss) not in vis:\n",
    "                        vis.add((xx,yy,ss))\n",
    "                        q.appendleft((xx,yy,ss))\n",
    "\n",
    "        return sorted(ans[1:])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, p: List[int], t: List[List[int]], o: List[List[int]]) -> List[List[int]]:\n",
    "        visit = defaultdict(set)\n",
    "        visit[(p[0],p[1])].add(1)\n",
    "        tmp = [(p[0],p[1], 1)]\n",
    "        l1,l2 = len(t),len(t[0])\n",
    "        sx = [[0]*l2 for i in range(l1)]\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                sx[i][j] = t[i][j]+o[i][j]\n",
    "        res = []\n",
    "        while tmp:\n",
    "            a,b,q = tmp.pop()\n",
    "            if q==1:\n",
    "                res.append([a,b])\n",
    "            for da,db in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                c,d = a+da, b+db\n",
    "                if 0<=c<l1 and 0<=d<l2 and (q + t[a][b] - sx[c][d])>0:\n",
    "                    if (q + t[a][b] - sx[c][d]) not in visit[(c,d)]:\n",
    "                        cur = q + t[a][b] - sx[c][d]\n",
    "                        visit[(c,d)].add(cur)\n",
    "                        tmp.append((c,d,cur))\n",
    "        return sorted(res[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        stack=[]\n",
    "        stack.append(position+[1])\n",
    "        visited=set()\n",
    "       \n",
    "        visited.add((position[0],position[1],1))\n",
    "        ans=[]\n",
    "        #ans.append(position)\n",
    "        row=len(terrain)\n",
    "        col=len(terrain[0])\n",
    "        while stack:\n",
    "            x,y,speed=stack.pop(0)\n",
    "            if speed==1:\n",
    "                ans.append([x,y])\n",
    "            h=terrain[x][y]\n",
    "            for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if 0<=x1<row and 0<=y1<col:\n",
    "                    newspeed=speed+h-terrain[x1][y1]-obstacle[x1][y1]\n",
    "                    #if newspeed<1:\n",
    "                       # newspeed=1\n",
    "                    if (x1,y1,newspeed) not in visited and newspeed>0:\n",
    "                        stack.append([x1,y1,newspeed])\n",
    "                        visited.add((x1,y1,newspeed))\n",
    "        \n",
    "        return sorted(ans[1:])\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, p: List[int], t: List[List[int]], o: List[List[int]]) -> List[List[int]]:\n",
    "        visit = defaultdict(set)\n",
    "        visit[(p[0],p[1])].add(1)\n",
    "        tmp = [(p[0],p[1], 1)]\n",
    "        l1,l2 = len(t),len(t[0])\n",
    "        sx = [[0]*l2 for i in range(l1)]\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                sx[i][j] = t[i][j]+o[i][j]\n",
    "        res = []\n",
    "        while tmp:\n",
    "            a,b,q = tmp.pop()\n",
    "            if q==1:\n",
    "                res.append([a,b])\n",
    "            for da,db in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                c,d = a+da, b+db\n",
    "                if 0<=c<l1 and 0<=d<l2:\n",
    "                    cur = q + t[a][b] - sx[c][d]\n",
    "                    if cur not in visit[(c,d)] and cur>0:\n",
    "                        visit[(c,d)].add(cur)\n",
    "                        tmp.append((c,d,cur))\n",
    "        return sorted(res[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m = len(terrain)\n",
    "        n = len(terrain[0])\n",
    "\n",
    "        q = deque()\n",
    "        q.append((position[0], position[1], 1))\n",
    "        vis = set()\n",
    "        vis.add((position[0], position[1], 1))\n",
    "        res = []\n",
    "\n",
    "        while q:\n",
    "            x, y, s = q.popleft()\n",
    "            if s == 1:\n",
    "                res.append([x, y])\n",
    "            for dx, dy in (x-1, y), (x+1, y), (x, y-1), (x, y+1):\n",
    "                if 0 <= dx <= m-1 and 0 <= dy <= n-1:\n",
    "                    new_s = s + terrain[x][y] - terrain[dx][dy] - obstacle[dx][dy]\n",
    "                    if new_s > 0 and (dx, dy, new_s) not in vis:\n",
    "                        vis.add((dx, dy, new_s))\n",
    "                        q.append((dx, dy, new_s))\n",
    "        \n",
    "        return sorted(res[1:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, p: List[int], t: List[List[int]], o: List[List[int]]) -> List[List[int]]:\n",
    "        visit = defaultdict(set)\n",
    "        visit[(p[0],p[1])].add(1)\n",
    "        tmp = [(p[0],p[1], 1)]\n",
    "        l1,l2 = len(t),len(t[0])\n",
    "        sx = [[0]*l2 for i in range(l1)]\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                sx[i][j] = t[i][j]+o[i][j]\n",
    "        res = []\n",
    "        x = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        while tmp:\n",
    "            a,b,q = tmp.pop()\n",
    "            if q==1:\n",
    "                res.append([a,b])\n",
    "            for da,db in x:\n",
    "                c,d = a+da, b+db\n",
    "                if 0<=c<l1 and 0<=d<l2:\n",
    "                    cur = q + t[a][b] - sx[c][d]\n",
    "                    if cur not in visit[(c,d)] and cur>0:\n",
    "                        visit[(c,d)].add(cur)\n",
    "                        tmp.append((c,d,cur))\n",
    "        return sorted(res[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, p: List[int], t: List[List[int]], o: List[List[int]]) -> List[List[int]]:\n",
    "        visit = defaultdict(set)\n",
    "        visit[(p[0],p[1])].add(1)\n",
    "        tmp = [(p[0],p[1], 1)]\n",
    "        l1,l2 = len(t),len(t[0])\n",
    "        sx = [[0]*l2 for i in range(l1)]\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                sx[i][j] = t[i][j]+o[i][j]\n",
    "        res = []\n",
    "        while tmp:\n",
    "            a,b,q = tmp.pop()\n",
    "            if q==1:\n",
    "                res.append([a,b])\n",
    "            for da,db in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                c,d = a+da, b+db\n",
    "                if 0<=c<l1 and 0<=d<l2:\n",
    "                    cur = q + t[a][b] - sx[c][d]\n",
    "                    if cur not in visit[(c,d)] and cur>0:\n",
    "                        visit[(c,d)].add(cur)\n",
    "                        tmp.append((c,d,cur))\n",
    "        return sorted(res[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(terrain), len(terrain[0])\n",
    "        vis = set()\n",
    "        q = deque([(position[0], position[1], 1)])\n",
    "        vis.add((position[0], position[1], 1))\n",
    "        ans = []\n",
    "        while q:\n",
    "            i, j, s = q.popleft()\n",
    "            for r, c in (i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                if 0<=r<m and 0<=c<n:\n",
    "                    v = s + terrain[i][j] - terrain[r][c] - obstacle[r][c]\n",
    "                    if v > 0 and (r, c, v) not in vis:\n",
    "                        if v == 1:\n",
    "                            ans.append([r, c])\n",
    "                        q.append((r, c, v))\n",
    "                        vis.add((r, c, v))\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        dir=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        n,m=len(terrain),len(terrain[0])\n",
    "        ans=[]\n",
    "        vis=set()\n",
    "        q=deque()\n",
    "        q.appendleft((position[0],position[1],1))\n",
    "        vis.add((position[0],position[1],1))\n",
    "        while q:\n",
    "            x,y,s=q.pop()\n",
    "            if s==1:\n",
    "                ans.append([x,y])\n",
    "            for i in dir:\n",
    "                xx,yy=x+i[0],y+i[1]\n",
    "                if n>xx and xx>=0 and m>yy and yy>=0 and s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]>0:\n",
    "                    ss=s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]\n",
    "                    if (xx,yy,ss) not in vis:\n",
    "                        vis.add((xx,yy,ss))\n",
    "                        q.appendleft((xx,yy,ss))\n",
    "        \n",
    "        return sorted(ans[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n,m=len(terrain),len(terrain[0])\n",
    "        vis=set()\n",
    "        q=deque()\n",
    "        # 状态DFS需要带上状态,即速度\n",
    "        q.appendleft((position[0],position[1],1))\n",
    "        vis.add((position[0],position[1],1))\n",
    "        ans=[]\n",
    "        while q:\n",
    "            x,y,s=q.pop()\n",
    "            if s==1:\n",
    "                ans.append(list((x,y)))\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if n>xx>=0<=yy<m and s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]>0:\n",
    "                    ss=s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]\n",
    "                    if (xx,yy,ss) not in vis:\n",
    "                        vis.add((xx,yy,ss))\n",
    "                        q.appendleft((xx,yy,ss))\n",
    "\n",
    "        return sorted(ans[1:])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import numpy as np\n",
    "# class Solution:\n",
    "#     def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "#         diraction = [[-1, 0], [0, -1], [1, 0], [0, 1]] ##上左下右\n",
    "#         n = len(terrain)\n",
    "#         m = len(terrain[0])\n",
    "#         visit = list()\n",
    "#         def dfs(x: int, y: int, v: int):\n",
    "#             if v <= 0:\n",
    "#                 return\n",
    "#             visit.append([x, y, v])\n",
    "#             if v == 1 and not [x,y] in ans and (x != position[0] or y != position[1]):\n",
    "#                 ans.append([x,y])\n",
    "#             for d in diraction:\n",
    "#                 if (x + d[0] >= 0 and x + d[0] < n) and (y + d[1] >= 0 and y + d[1] < m):\n",
    "#                     curr = v + terrain[x][y] - terrain[x + d[0]][y + d[1]] - obstacle[x + d[0]][y + d[1]]\n",
    "#                     if [x + d[0], y + d[1], curr] in visit:\n",
    "#                         continue\n",
    "#                     dfs(x + d[0], y + d[1], curr)\n",
    "#         ans = list()\n",
    "#         dfs(position[0], position[1], 1)\n",
    "#         ans.sort()\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n,m=len(terrain),len(terrain[0])\n",
    "        vis=set()\n",
    "        q=deque()\n",
    "        # 状态DFS需要带上状态,即速度\n",
    "        q.appendleft((position[0],position[1],1))\n",
    "        vis.add((position[0],position[1],1))\n",
    "        ans=[]\n",
    "        while q:\n",
    "            x,y,s=q.pop()\n",
    "            if s==1:\n",
    "                ans.append(list((x,y)))\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if n>xx>=0<=yy<m and s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]>0:\n",
    "                    ss=s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]\n",
    "                    if (xx,yy,ss) not in vis:\n",
    "                        vis.add((xx,yy,ss))\n",
    "                        q.appendleft((xx,yy,ss))\n",
    "\n",
    "        return sorted(ans[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        # 查看网友的写法，并进一步修改之后\n",
    "        n,m=len(terrain),len(terrain[0])\n",
    "        vis=set()\n",
    "        q=deque()\n",
    "        # 状态DFS需要带上状态,即速度\n",
    "        q.appendleft((position[0],position[1],1))\n",
    "        vis.add((position[0],position[1],1))\n",
    "        ans=[]\n",
    "        while q:\n",
    "            x,y,s=q.pop()\n",
    "            if s==1:\n",
    "                ans.append(list((x,y)))\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if n>xx>=0<=yy<m and s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]>0:\n",
    "                    ss=s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]\n",
    "                    if (xx,yy,ss) not in vis:\n",
    "                        vis.add((xx,yy,ss))\n",
    "                        q.appendleft((xx,yy,ss))\n",
    "\n",
    "        return sorted(ans[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, p: List[int], t: List[List[int]], o: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        s = [[p[0], p[1], 1]]\n",
    "        vis = {(p[0], p[1], 1)}\n",
    "        m = len(t)\n",
    "        n = len(t[0])\n",
    "        ans = set([])\n",
    "        while s:\n",
    "            tmp = []\n",
    "            for i, j, v in s:\n",
    "       \n",
    "                for x, y in [[0,1], [0,-1], [1,0], [-1,0]]:\n",
    "                    x += i \n",
    "                    y += j \n",
    "                    if (0<=x<m) and (0<=y<n):\n",
    "                        nv = v + t[i][j] - t[x][y] - o[x][y]\n",
    "                        if nv>0:\n",
    "                         \n",
    "                            if (x, y, nv) not in vis:\n",
    "                                vis.add((x, y, nv))\n",
    "                                tmp.append((x, y, nv))\n",
    "                s = tmp \n",
    "        p = tuple(p)\n",
    "        for i, j, v in vis:\n",
    "            if v==1:\n",
    "                if (i, j)!=p:\n",
    "                    ans.add((i, j))\n",
    "        ans = sorted([[i,j] for i, j in ans])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        vis = set()\n",
    "        q = collections.deque()\n",
    "        n = len(terrain)\n",
    "        m = len(terrain[0])\n",
    "\n",
    "        q.append((position[0],position[1],1))\n",
    "        vis.add((position[0],position[1],1))\n",
    "        ans=[]\n",
    "        while q:\n",
    "            x,y,s=q.pop()\n",
    "            if s==1:\n",
    "                ans.append(list((x,y)))\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if n>xx>=0<=yy<m and s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]>0:\n",
    "                    ss=s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]\n",
    "                    if (xx,yy,ss) not in vis:\n",
    "                        vis.add((xx,yy,ss))\n",
    "                        q.append((xx,yy,ss))\n",
    "\n",
    "        return sorted(ans[1:])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, p: List[int], t: List[List[int]], o: List[List[int]]) -> List[List[int]]:\n",
    "        visit = defaultdict(set)\n",
    "        visit[(p[0],p[1])].add(1)\n",
    "        tmp = [(p[0],p[1], 1)]\n",
    "        l1,l2 = len(t),len(t[0])\n",
    "        sx = [[0]*l2 for i in range(l1)]\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                sx[i][j] = t[i][j]+o[i][j]\n",
    "        res = []\n",
    "        while tmp:\n",
    "            a,b,q = tmp.pop()\n",
    "            if q==1:\n",
    "                res.append([a,b])\n",
    "            for da,db in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                c,d = a+da, b+db\n",
    "                if 0<=c<l1 and 0<=d<l2:\n",
    "                    if (q + t[a][b] - sx[c][d]) not in visit[(c,d)] and (q + t[a][b] - sx[c][d])>0:\n",
    "                        cur = q + t[a][b] - sx[c][d]\n",
    "                        visit[(c,d)].add(cur)\n",
    "                        tmp.append((c,d,cur))\n",
    "        return sorted(res[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        # 查看网友的写法，并进一步修改之后\n",
    "        n,m = len(terrain),len(terrain[0])\n",
    "        ans = list()\n",
    "        visited = set()\n",
    "        dq = deque()\n",
    "        visited.add((position[0],position[1],1))\n",
    "        dq.append((position[0],position[1],1))\n",
    "        directions = [(0,1),(0,-1),(-1,0),(1,0)]\n",
    "        while dq:\n",
    "            x0,y0,v0 = dq.popleft()\n",
    "            if v0 == 1:\n",
    "                ans.append([x0, y0])\n",
    "            for i,j in directions:\n",
    "                x = x0 + i\n",
    "                y = y0 + j\n",
    "                if 0 <= x <n and 0 <= y < m and terrain[x0][y0] - terrain[x][y] - obstacle[x][y] + v0 > 0:\n",
    "                    v = terrain[x0][y0] - terrain[x][y] - obstacle[x][y] + v0\n",
    "                    if (x,y,v) not in visited:\n",
    "                        visited.add((x,y,v))\n",
    "                        dq.append((x,y,v))\n",
    "        return sorted(ans[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(terrain)\n",
    "        m = len(terrain[0])\n",
    "\n",
    "        q = deque([(position[0], position[1], 1)])\n",
    "        vis = {(position[0], position[1], 1)}\n",
    "        ans = []\n",
    "\n",
    "        while q:\n",
    "            x, y, s = q.popleft()\n",
    "            if s == 1:\n",
    "                ans.append([x, y])\n",
    "            for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n and 0 <= ny < m:\n",
    "                    ns = s + terrain[x][y] - terrain[nx][ny] - obstacle[nx][ny]\n",
    "                    if ns <= 0 or (nx, ny, ns) in vis:\n",
    "                        continue\n",
    "                    vis.add((nx, ny, ns))\n",
    "                    q.append((nx, ny, ns))\n",
    "        \n",
    "        return sorted(ans[1:])\n",
    "        \n",
    "\n",
    "        # ans = []\n",
    "        # vis = []\n",
    "        # @cache\n",
    "        # def dfs(r, c, v):\n",
    "        #     if [r, c] in vis:\n",
    "        #         return\n",
    "        #     vis.append([r, c])\n",
    "        #     if v <= 0:\n",
    "        #         return\n",
    "        #     if [r, c] != position and v == 1:\n",
    "        #         ans.append([r, c])\n",
    "        #     h1 = terrain[r][c]\n",
    "        #     if r + 1 < n:\n",
    "        #         h2 = terrain[r + 1][c]\n",
    "        #         o2 = obstacle[r + 1][c]\n",
    "        #         dfs(r + 1, c, v + h1 - h2 - o2)\n",
    "        #     if r - 1 >= 0:\n",
    "        #         h2 = terrain[r - 1][c]\n",
    "        #         o2 = obstacle[r - 1][c]\n",
    "        #         dfs(r - 1, c, v + h1 - h2 - o2)\n",
    "        #     if c + 1 < m:\n",
    "        #         h2 = terrain[r][c + 1]\n",
    "        #         o2 = obstacle[r][c + 1]\n",
    "        #         dfs(r, c + 1, v + h1 - h2 - o2)\n",
    "        #     if c - 1 >= 0:\n",
    "        #         h2 = terrain[r][c - 1]\n",
    "        #         o2 = obstacle[r][c - 1]\n",
    "        #         dfs(r, c - 1, v + h1 - h2 - o2)\n",
    "        \n",
    "        # dfs(position[0], position[1], 1)\n",
    "        # dfs.cache_clear()\n",
    "        # ans.sort(key = lambda x: (x[0], x[1]))\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, p: List[int], t: List[List[int]], o: List[List[int]]) -> List[List[int]]:\n",
    "        visit = defaultdict(set)\n",
    "        visit[(p[0],p[1])].add(1)\n",
    "        tmp = [(p[0],p[1], 1)]\n",
    "        l1,l2 = len(t),len(t[0])\n",
    "        sx = [[0]*l2 for i in range(l1)]\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                sx[i][j] = t[i][j]+o[i][j]\n",
    "        res = []\n",
    "        while tmp:\n",
    "            a,b,q = tmp.pop()\n",
    "            if q==1:\n",
    "                res.append([a,b])\n",
    "            for da,db in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                c,d = a+da, b+db\n",
    "                if 0<=c<l1 and 0<=d<l2 and (q + t[a][b] - sx[c][d])>0:\n",
    "                    cur = q + t[a][b] - sx[c][d]\n",
    "                    if cur not in visit[(c,d)]:\n",
    "                        visit[(c,d)].add(cur)\n",
    "                        tmp.append((c,d,cur))\n",
    "        return sorted(res[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        ref = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        n=len(terrain)\n",
    "        m=len(terrain[0])\n",
    "        res = []\n",
    "        def bfs(x,y,speed):\n",
    "            nonlocal res, n,m\n",
    "            queue = [(x,y,speed)]\n",
    "            vis = {(x,y,speed)}\n",
    "            while queue:\n",
    "                curx, cury, v = queue.pop(0)\n",
    "                if v==speed:\n",
    "                    res.append([curx,cury])\n",
    "                \n",
    "                for i,j in ref:\n",
    "                    nextx = curx + i\n",
    "                    nexty = cury + j\n",
    "                    \n",
    "                    if 0<=nextx<n and 0<=nexty<m:\n",
    "                        nextv = v + terrain[curx][cury] - terrain[nextx][nexty] - obstacle[nextx][nexty]\n",
    "                        if nextv>0 and (nextx,nexty,nextv) not in vis:\n",
    "                            vis.add((nextx,nexty, nextv))\n",
    "                            queue.append((nextx,nexty,nextv))\n",
    "            return\n",
    "        \n",
    "        bfs(position[0], position[1], 1)\n",
    "        res = res[1:]\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bicycleYard(self, pos: List[int], H: List[List[int]], O: List[List[int]]) -> List[List[int]]:\r\n",
    "        n, m = len(H), len(H[0])\r\n",
    "        q = [(pos[0], pos[1], 1)]\r\n",
    "        seen, res = set(q), []\r\n",
    "        while q:\r\n",
    "            x, y, v = q.pop()\r\n",
    "            for nx, ny in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:\r\n",
    "                if 0 <= nx < n and 0 <= ny < m:\r\n",
    "                    nv = v + H[x][y] - H[nx][ny] - O[nx][ny]\r\n",
    "                    if nv <= 0 or (nx, ny, nv) in seen: continue\r\n",
    "                    if nv == 1: res.append([nx, ny])\r\n",
    "                    seen.add((nx, ny, nv))\r\n",
    "                    q.append((nx, ny, nv))\r\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n,m=len(terrain),len(terrain[0])\n",
    "        vis=set()\n",
    "        q=deque()\n",
    "        # 状态DFS需要带上状态,即速度\n",
    "        q.appendleft((position[0],position[1],1))\n",
    "        vis.add((position[0],position[1],1))\n",
    "        ans=[]\n",
    "        while q:\n",
    "            x,y,s=q.pop()\n",
    "            if s==1:\n",
    "                ans.append(list((x,y)))\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if n>xx>=0<=yy<m and s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]>0:\n",
    "                    ss=s+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]\n",
    "                    if (xx,yy,ss) not in vis:\n",
    "                        vis.add((xx,yy,ss))\n",
    "                        q.appendleft((xx,yy,ss))\n",
    "\n",
    "        return sorted(ans[1:])\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        n, m = len(terrain), len(terrain[0])\n",
    "        vis = defaultdict(int)\n",
    "        def isValid(x,y):\n",
    "            return 0<=x<n and 0<=y<m\n",
    "        Q = [(position[0], position[1], 1)]\n",
    "        vis[(position[0], position[1], 1)] = 1\n",
    "        ans = []\n",
    "        while Q:\n",
    "            x,y,v = Q.pop(0)\n",
    "\n",
    "            for [nx, ny] in [[x+1,y], [x-1, y], [x,y+1], [x,y-1]]:\n",
    "                if isValid(nx,ny):\n",
    "                    nv = v + terrain[x][y] - terrain[nx][ny] - obstacle[nx][ny]\n",
    "                    if nv > 0 and not vis[(nx,ny,nv)]:\n",
    "                        vis[(nx,ny,nv)] = 1\n",
    "                        Q.append((nx,ny,nv))\n",
    "                        if nv == 1:\n",
    "                            ans.append([nx,ny])\n",
    "        ans.sort()\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(terrain)\n",
    "        n = len(terrain[0])\n",
    "        steps = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n",
    "        visited = set()\n",
    "        q = collections.deque([(position[0], position[1], 1)])\n",
    "        visited.add(q[0])\n",
    "        ans = []\n",
    "        while q:\n",
    "            x, y, v = q.popleft()\n",
    "            #print(x, y, v)\n",
    "            for xx, yy in steps:\n",
    "                newX = x + xx\n",
    "                newY = y + yy\n",
    "                if 0 <= newX < m and 0 <= newY < n:\n",
    "                    newV = v + terrain[x][y] - terrain[newX][newY] - obstacle[newX][newY]\n",
    "                    if newV >= 1 and (newX, newY, newV) not in visited:\n",
    "                        q.append((newX, newY, newV))\n",
    "\n",
    "                        visited.add((newX, newY, newV))\n",
    "\n",
    "                        if newV == 1:\n",
    "                            ans.append([newX, newY])\n",
    "                            \n",
    "        ans.sort(key = lambda x: (x[0], x[1]))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, p: List[int], t: List[List[int]], o: List[List[int]]) -> List[List[int]]:\n",
    "        visit = defaultdict(set)\n",
    "        visit[(p[0],p[1])].add(1)\n",
    "        tmp = [(p[0],p[1], 1)]\n",
    "        l1,l2 = len(t),len(t[0])\n",
    "        sx = [[0]*l2 for i in range(l1)]\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                sx[i][j] = t[i][j]+o[i][j]\n",
    "        res = []\n",
    "        while tmp:\n",
    "            a,b,q = tmp.pop()\n",
    "            if q==1:\n",
    "                res.append([a,b])\n",
    "            for da,db in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                c,d = a+da, b+db\n",
    "                if 0<=c<l1 and 0<=d<l2:\n",
    "                    cur = q + t[a][b] - sx[c][d]\n",
    "                    if cur not in visit[(c,d)] and cur>0:\n",
    "                        visit[(c,d)].add(cur)\n",
    "                        tmp.append((c,d,cur))\n",
    "        return sorted(res[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        rows, cols = len(terrain), len(terrain[0])\n",
    "        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        \n",
    "        # 记录已访问的 (位置, 速度)\n",
    "        visited = set()\n",
    "        \n",
    "        # 用于记录速度为1且不是初始位置的所有位置\n",
    "        ans = []\n",
    "        \n",
    "        # 使用双端队列保存待处理的 (位置, 速度)\n",
    "        q = deque([(position, 1)])\n",
    "        \n",
    "        while q:\n",
    "            (x, y), speed = q.popleft()\n",
    "            \n",
    "            if (x, y, speed) in visited:\n",
    "                continue\n",
    "            \n",
    "            visited.add((x, y, speed))\n",
    "            \n",
    "            if speed == 1 and (x, y) != tuple(position):\n",
    "                ans.append([x, y])\n",
    "            \n",
    "            for dx, dy in directions:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < rows and 0 <= ny < cols:\n",
    "                    new_speed = speed + terrain[x][y] - terrain[nx][ny] - obstacle[nx][ny]\n",
    "                    if new_speed > 0:\n",
    "                        q.append(((nx, ny), new_speed))\n",
    "        \n",
    "        return sorted(ans)  # 按行、列坐标升序排列\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "position = [0, 0]\n",
    "terrain = [[0, 0], [0, 0]]\n",
    "obstacle = [[0, 0], [0, 0]]\n",
    "print(sol.bicycleYard(position, terrain, obstacle))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        visited=defaultdict(list)\n",
    "        m=len(terrain)\n",
    "        n=len(terrain[0])\n",
    "        ans=[]\n",
    "        node=[]\n",
    "        def dfs(pos, speed):\n",
    "            if speed<=0 or speed in visited[pos]:\n",
    "                return \n",
    "            if speed==1:\n",
    "                ans.append(list(pos))\n",
    "            visited[pos].append(speed)\n",
    "            x,y=pos\n",
    "            for nx,ny in (x+1,y),(x-1,y),(x,y-1),(x,y+1):\n",
    "                if 0<=nx<m and 0<=ny<n:\n",
    "                    h1 = terrain[x][y]\n",
    "                    h2 = terrain[nx][ny]\n",
    "                    o2 = obstacle[nx][ny]\n",
    "                    new_speed = speed + h1 - h2 - o2\n",
    "                    dfs((nx,ny),new_speed)\n",
    "        p=tuple(position)\n",
    "        dfs(p, 1)\n",
    "        ans.remove(position)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        record = set()\n",
    "        res = set()\n",
    "        m = len(terrain)\n",
    "        n = len(terrain[0])\n",
    "        def dfs(i,j,v):\n",
    "            record.add((i, j, v))\n",
    "            t = terrain[i][j]\n",
    "            for ii in range(i-1, i+2):\n",
    "                for jj in range(j-1, j+2):\n",
    "                    if ii != i and jj != j:\n",
    "                        continue\n",
    "                    if ii == i and jj == j:\n",
    "                        continue\n",
    "                    if 0 <= ii < m and 0 <= jj < n:\n",
    "                        v1 = v + t - terrain[ii][jj] - obstacle[ii][jj]\n",
    "                        if (ii, jj, v1) in record:\n",
    "                            continue\n",
    "                        if v1 == 1:\n",
    "                            res.add((ii, jj))\n",
    "                        if v1 > 0:\n",
    "                            dfs(ii, jj, v1)\n",
    "        dfs(position[0], position[1], 1)\n",
    "        return list([i, j] for i, j in sorted(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(1000000)\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(terrain),len(terrain[0])\n",
    "        c=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        d=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        s=set()\n",
    "        find=set()\n",
    "        def dfs(x,y,v):\n",
    "            #print(x,y,v)\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return\n",
    "            if (x,y,v)in find:\n",
    "                return \n",
    "            if v<=0:\n",
    "                return \n",
    "            find.add((x,y,v))\n",
    "            for d1,d2 in d:\n",
    "                xx=x+d1 \n",
    "                yy=y+d2\n",
    "                #print(xx,yy)\n",
    "                if xx<0 or yy<0 or xx>=m or yy>=n:\n",
    "                    continue\n",
    "                vv=v+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]\n",
    "                #print(xx,yy,vv)\n",
    "                if vv<=0:\n",
    "                    continue \n",
    "                if vv==1:\n",
    "                    s.add((xx,yy))\n",
    "                    dfs(xx,yy,vv)\n",
    "                else:\n",
    "                    dfs(xx,yy,vv) \n",
    "        dfs(position[0],position[1],1)\n",
    "        ans=list(s)\n",
    "        ans.sort()\n",
    "        #print(ans)\n",
    "        if (position[0],position[1]) in ans:\n",
    "            ans.remove((position[0],position[1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        v = set()\n",
    "        r = set()\n",
    "        def dfs(i,j,d):\n",
    "            if d == 1:\n",
    "                r.add((i,j))\n",
    "            for dx,dy in ((1,0), (-1,0), (0, 1), (0, -1)):\n",
    "                x,y = dx+i, dy+j\n",
    "                if 0<=x<len(terrain) and 0<=y<len(terrain[0]):\n",
    "                    h1 = terrain[i][j]\n",
    "                    h2 = terrain[x][y]\n",
    "                    o2 = obstacle[x][y]\n",
    "                    t = d+h1-h2-o2\n",
    "                    if t > 0 and (x,y,t) not in v:\n",
    "                        v.add((x,y,t))\n",
    "                        dfs(x,y,t)\n",
    "        dfs(*position,1)\n",
    "        r.remove(tuple(position))\n",
    "        r = list(r)\n",
    "        return sorted(r)\n",
    "                \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(1000000)\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(terrain),len(terrain[0])\n",
    "        c=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        d=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        s=set()\n",
    "        find=set()\n",
    "        @cache\n",
    "        def dfs(x,y,v):\n",
    "            #print(x,y,v)\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return\n",
    "            if (x,y,v)in find:\n",
    "                return \n",
    "            if v<=0:\n",
    "                return \n",
    "            find.add((x,y,v))\n",
    "            for d1,d2 in d:\n",
    "                xx=x+d1 \n",
    "                yy=y+d2\n",
    "                #print(xx,yy)\n",
    "                if xx<0 or yy<0 or xx>=m or yy>=n:\n",
    "                    continue\n",
    "                vv=v+terrain[x][y]-terrain[xx][yy]-obstacle[xx][yy]\n",
    "                #print(xx,yy,vv)\n",
    "                if vv<=0:\n",
    "                    continue \n",
    "                if vv==1:\n",
    "                    s.add((xx,yy))\n",
    "                    dfs(xx,yy,vv)\n",
    "                else:\n",
    "                    dfs(xx,yy,vv) \n",
    "        dfs(position[0],position[1],1)\n",
    "        ans=list(s)\n",
    "        ans.sort()\n",
    "        #print(ans)\n",
    "        if (position[0],position[1]) in ans:\n",
    "            ans.remove((position[0],position[1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(terrain)\n",
    "        n = len(terrain[0])\n",
    "        ans = set()\n",
    "        visited = set()\n",
    "        def dfs(cur, v):\n",
    "            visited.add((cur, v))\n",
    "            if v == 1:\n",
    "                ans.add(cur)\n",
    "            for nxt in [(cur[0]-1, cur[1]), (cur[0]+1, cur[1]),(cur[0], cur[1]-1),(cur[0], cur[1]+1)]:\n",
    "                if 0 <= nxt[0] < m and 0 <= nxt[1] < n and v + terrain[cur[0]][cur[1]] - terrain[nxt[0]][nxt[1]] - obstacle[nxt[0]][nxt[1]] > 0 and (nxt, v + terrain[cur[0]][cur[1]] - terrain[nxt[0]][nxt[1]] - obstacle[nxt[0]][nxt[1]]) not in visited:\n",
    "                    dfs(nxt, v + terrain[cur[0]][cur[1]] - terrain[nxt[0]][nxt[1]] - obstacle[nxt[0]][nxt[1]])\n",
    "        \n",
    "        dfs(tuple(position), 1)\n",
    "        ans -= {(tuple(position))}\n",
    "        return sorted(list(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(terrain)\n",
    "        m = len(terrain[0])\n",
    "\n",
    "        # q = deque([(position[0], position[1], 1)])\n",
    "        # vis = {(position[0], position[1], 1)}\n",
    "        # ans = []\n",
    "\n",
    "        # while q:\n",
    "        #     x, y, s = q.popleft()\n",
    "        #     if s == 1:\n",
    "        #         ans.append([x, y])\n",
    "        #     for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):\n",
    "        #         nx, ny = x + dx, y + dy\n",
    "        #         if 0 <= nx < n and 0 <= ny < m:\n",
    "        #             ns = s + terrain[x][y] - terrain[nx][ny] - obstacle[nx][ny]\n",
    "        #             if ns <= 0 or (nx, ny, ns) in vis:\n",
    "        #                 continue\n",
    "        #             vis.add((nx, ny, ns))\n",
    "        #             q.append((nx, ny, ns))\n",
    "        \n",
    "        # return sorted(ans[1:])\n",
    "        \n",
    "\n",
    "        ans = []\n",
    "        vis = []\n",
    "        #@cache\n",
    "        def dfs(r, c, v):\n",
    "            if [r, c, v] in vis:\n",
    "                return\n",
    "            vis.append([r, c, v])\n",
    "            if v <= 0:\n",
    "                return\n",
    "            if [r, c] != position and v == 1:\n",
    "                ans.append([r, c])\n",
    "            h1 = terrain[r][c]\n",
    "            if r + 1 < n:\n",
    "                h2 = terrain[r + 1][c]\n",
    "                o2 = obstacle[r + 1][c]\n",
    "                dfs(r + 1, c, v + h1 - h2 - o2)\n",
    "            if r - 1 >= 0:\n",
    "                h2 = terrain[r - 1][c]\n",
    "                o2 = obstacle[r - 1][c]\n",
    "                dfs(r - 1, c, v + h1 - h2 - o2)\n",
    "            if c + 1 < m:\n",
    "                h2 = terrain[r][c + 1]\n",
    "                o2 = obstacle[r][c + 1]\n",
    "                dfs(r, c + 1, v + h1 - h2 - o2)\n",
    "            if c - 1 >= 0:\n",
    "                h2 = terrain[r][c - 1]\n",
    "                o2 = obstacle[r][c - 1]\n",
    "                dfs(r, c - 1, v + h1 - h2 - o2)\n",
    "        \n",
    "        dfs(position[0], position[1], 1)\n",
    "        #dfs.cache_clear()\n",
    "        ans.sort(key = lambda x: (x[0], x[1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(terrain)\n",
    "        m = len(terrain[0])\n",
    "\n",
    "        # q = deque([(position[0], position[1], 1)])\n",
    "        # vis = {(position[0], position[1], 1)}\n",
    "        # ans = []\n",
    "\n",
    "        # while q:\n",
    "        #     x, y, s = q.popleft()\n",
    "        #     if s == 1:\n",
    "        #         ans.append([x, y])\n",
    "        #     for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):\n",
    "        #         nx, ny = x + dx, y + dy\n",
    "        #         if 0 <= nx < n and 0 <= ny < m:\n",
    "        #             ns = s + terrain[x][y] - terrain[nx][ny] - obstacle[nx][ny]\n",
    "        #             if ns <= 0 or (nx, ny, ns) in vis:\n",
    "        #                 continue\n",
    "        #             vis.add((nx, ny, ns))\n",
    "        #             q.append((nx, ny, ns))\n",
    "        \n",
    "        # return sorted(ans[1:])\n",
    "        \n",
    "\n",
    "        ans = []\n",
    "        vis = []\n",
    "        @cache\n",
    "        def dfs(r, c, v):\n",
    "            if [r, c, v] in vis:\n",
    "                return\n",
    "            vis.append([r, c, v])\n",
    "            if v <= 0:\n",
    "                return\n",
    "            if [r, c] != position and v == 1:\n",
    "                ans.append([r, c])\n",
    "            h1 = terrain[r][c]\n",
    "            if r + 1 < n:\n",
    "                h2 = terrain[r + 1][c]\n",
    "                o2 = obstacle[r + 1][c]\n",
    "                dfs(r + 1, c, v + h1 - h2 - o2)\n",
    "            if r - 1 >= 0:\n",
    "                h2 = terrain[r - 1][c]\n",
    "                o2 = obstacle[r - 1][c]\n",
    "                dfs(r - 1, c, v + h1 - h2 - o2)\n",
    "            if c + 1 < m:\n",
    "                h2 = terrain[r][c + 1]\n",
    "                o2 = obstacle[r][c + 1]\n",
    "                dfs(r, c + 1, v + h1 - h2 - o2)\n",
    "            if c - 1 >= 0:\n",
    "                h2 = terrain[r][c - 1]\n",
    "                o2 = obstacle[r][c - 1]\n",
    "                dfs(r, c - 1, v + h1 - h2 - o2)\n",
    "        \n",
    "        dfs(position[0], position[1], 1)\n",
    "        dfs.cache_clear()\n",
    "        ans.sort(key = lambda x: (x[0], x[1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\r\n",
    "        Row = len(terrain)\r\n",
    "        Col = len(terrain[0])\r\n",
    "        \r\n",
    "        res = set()\r\n",
    "        visited = [[set() for _ in range(Col)] for _ in range(Row)]\r\n",
    "        sr, sc = position[0], position[1]\r\n",
    "        \r\n",
    "        q = collections.deque()\r\n",
    "        q.append((sr, sc, 1))\r\n",
    "        while q:\r\n",
    "            r, c, cur_speed = q.popleft()\r\n",
    "            if cur_speed in visited[r][c]:\r\n",
    "                continue\r\n",
    "            visited[r][c].add(cur_speed)\r\n",
    "            if (cur_speed == 1) and (r, c) != (position[0], position[1]):\r\n",
    "                res.add((r, c))\r\n",
    "                if len(res) == Row * Col:\r\n",
    "                    break\r\n",
    "            for nr, nc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:\r\n",
    "                if 0 <= nr < Row and 0 <= nc < Col:\r\n",
    "                    nxt_speed = terrain[r][c] - terrain[nr][nc] - obstacle[nr][nc] + cur_speed\r\n",
    "                    if nxt_speed > 0:\r\n",
    "                        q.append((nr, nc, nxt_speed))\r\n",
    "\r\n",
    "        return sorted(list(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "      n, m = len(terrain), len(terrain[0])\n",
    "      p = deque()\n",
    "      position.append(1)\n",
    "      p.append(position)\n",
    "      move = [[1,0], [0,-1], [-1,0], [0,1]]\n",
    "      ans = []\n",
    "      speed1 = [[set() for j in range(m)] for i in range(n)]\n",
    "      speed1[position[0]][position[1]].add(1)\n",
    "      while p:\n",
    "        x, y, speed = p.popleft()\n",
    "        for i, j in move:\n",
    "          x0 = x+i\n",
    "          y0 = y+j\n",
    "          if 0<=x0<n and 0<=y0<m:\n",
    "            speed0 = speed+terrain[x][y]-terrain[x0][y0]-obstacle[x0][y0]\n",
    "            if speed0>0 and speed0 not in speed1[x0][y0]:\n",
    "              if speed0==1 and (x0!=position[0] or y0!=position[1]):\n",
    "                ans.append([x0,y0])\n",
    "              speed1[x0][y0].add(speed0)\n",
    "              p.append([x0, y0, speed0])\n",
    "      return sorted(ans)\n",
    "\n",
    "\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(terrain), len(terrain[0])\n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        visited = [[{} for _ in range(m)] for _ in range(n)]\n",
    "        def dfs(pos, speed):\n",
    "            ans = []\n",
    "            if speed < 1:\n",
    "                return ans\n",
    "            if speed in visited[pos[0]][pos[1]]:\n",
    "                return ans\n",
    "            if speed == 1 and pos != position:\n",
    "                ans.append(pos)\n",
    "            \n",
    "            visited[pos[0]][pos[1]][speed] = 1\n",
    "            for x, y in dirs:\n",
    "                px = pos[0] + x\n",
    "                py = pos[1] + y\n",
    "                if 0 <= px < n and 0 <= py < m:\n",
    "                    diff_speed = obstacle[px][py]\n",
    "                    new_pos_height = terrain[px][py]\n",
    "                    pos_height = terrain[pos[0]][pos[1]]\n",
    "                    new_ans = dfs([px, py], pos_height - new_pos_height - diff_speed + speed)\n",
    "                    if new_ans:\n",
    "                        ans.extend(new_ans)\n",
    "            return ans\n",
    "\n",
    "        ans = dfs(position, 1)\n",
    "        ans.sort(key = lambda x: [x[0], x[1]])\n",
    "        # ans.remove(position)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(terrain), len(terrain[0])\n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        visited = [[{} for _ in range(m)] for _ in range(n)]\n",
    "        def dfs(pos, speed):\n",
    "            ans = []\n",
    "            if speed < 1:\n",
    "                return ans\n",
    "            if speed in visited[pos[0]][pos[1]]:\n",
    "                return ans\n",
    "            if speed == 1 and pos != position:\n",
    "                ans.append(pos)\n",
    "            \n",
    "            visited[pos[0]][pos[1]][speed] = 1\n",
    "            for x, y in dirs:\n",
    "                px = pos[0] + x\n",
    "                py = pos[1] + y\n",
    "                if 0 <= px < n and 0 <= py < m:\n",
    "                    diff_speed = obstacle[px][py]\n",
    "                    new_pos_height = terrain[px][py]\n",
    "                    pos_height = terrain[pos[0]][pos[1]]\n",
    "                    new_ans = dfs([px, py], pos_height - new_pos_height - diff_speed + speed)\n",
    "                    ans.extend(new_ans)\n",
    "            return ans\n",
    "\n",
    "        ans = dfs(position, 1)\n",
    "        ans.sort(key = lambda x: [x[0], x[1]])\n",
    "        # ans.remove(position)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(terrain), len(terrain[0])\n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        visited = [[{} for _ in range(m)] for _ in range(n)]\n",
    "        def dfs(pos, speed):\n",
    "            ans = []\n",
    "            if speed < 1:\n",
    "                return ans\n",
    "            if speed in visited[pos[0]][pos[1]]:\n",
    "                return ans\n",
    "            if speed == 1:\n",
    "                ans.append(pos)\n",
    "            \n",
    "            visited[pos[0]][pos[1]][speed] = 1\n",
    "            for x, y in dirs:\n",
    "                px = pos[0] + x\n",
    "                py = pos[1] + y\n",
    "                if 0 <= px < n and 0 <= py < m:\n",
    "                    diff_speed = obstacle[px][py]\n",
    "                    new_pos_height = terrain[px][py]\n",
    "                    pos_height = terrain[pos[0]][pos[1]]\n",
    "                    new_ans = dfs([px, py], pos_height - new_pos_height - diff_speed + speed)\n",
    "                    ans.extend(new_ans)\n",
    "            return ans\n",
    "\n",
    "        ans = dfs(position, 1)\n",
    "        ans.sort(key = lambda x: [x[0], x[1]])\n",
    "        ans.remove(position)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n,m=len(terrain),len(terrain[0])\n",
    "        mat=[[{} for i in range(m)] for j in range(n)]\n",
    "        x,y=position\n",
    "        st=set()\n",
    "        ans=set()\n",
    "        def dfs(pt,sp):\n",
    "            x,y=pt\n",
    "            if sp<=0 or sp>101  or mat[x][y].get(sp,0)==1:\n",
    "                return\n",
    "            if sp==1:\n",
    "                ans.add(pt)\n",
    "            mat[x][y][sp]=1\n",
    "            left,up,right,down = (x,y-1),(x-1,y),(x,y+1),(x+1,y)\n",
    "            lt=[left,up,right,down]\n",
    "            for p in lt:\n",
    "                if p[0]>=0 and p[0] <n and p[1]>=0 and p[1]<m:\n",
    "                    h1=terrain[x][y]\n",
    "                    h2=terrain[p[0]][p[1]]\n",
    "                    sp2=obstacle[p[0]][p[1]]\n",
    "                    dfs(p,sp+h1-h2-sp2)\n",
    "           \n",
    "        dfs((x,y),1)\n",
    "        if (position[0],position[1]) in ans:\n",
    "            ans.remove((position[0],position[1]))\n",
    "        print(ans)\n",
    "        return sorted( list(ans),key = lambda s:(s[0],s[1]) ,reverse=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        n,m=len(terrain),len(terrain[0])\n",
    "        mat=[[{} for i in range(m)] for j in range(n)]\n",
    "        x,y=position\n",
    "        st=set()\n",
    "        ans=set()\n",
    "        def dfs(pt,sp):\n",
    "            x,y=pt\n",
    "            if sp<=0 or sp>101  or mat[x][y].get(sp,0)==1:\n",
    "                return\n",
    "         \n",
    "            if sp==1:\n",
    "                ans.add(pt)\n",
    "            mat[x][y][sp]=1\n",
    "            left,up,right,down = (x,y-1),(x-1,y),(x,y+1),(x+1,y)\n",
    "            lt=[left,up,right,down]\n",
    "            for p in lt:\n",
    "                if p[0]>=0 and p[0] <n and p[1]>=0 and p[1]<m:\n",
    "                    h1=terrain[x][y]\n",
    "                    h2=terrain[p[0]][p[1]]\n",
    "                    sp2=obstacle[p[0]][p[1]]\n",
    "                    dfs(p,sp+h1-h2-sp2)\n",
    "           \n",
    "        dfs((x,y),1)\n",
    "        if (position[0],position[1]) in ans:\n",
    "            ans.remove((position[0],position[1]))\n",
    "        print(ans)\n",
    "        return sorted( list(ans),key = lambda s:(s[0],s[1]) ,reverse=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        diraction = [[-1, 0], [0, -1], [1, 0], [0, 1]] ##上左下右\n",
    "        n = len(terrain)\n",
    "        m = len(terrain[0])\n",
    "        visit = list()\n",
    "        # visit.append([position[0], [position[1], 1])\n",
    "        # visit[position[0]][position[1]] = 1\n",
    "        # count = Counter()\n",
    "        def dfs(x: int, y: int, v: int):\n",
    "            if v <= 0:\n",
    "                return\n",
    "            visit.append([x, y, v])\n",
    "            if v == 1 and not [x,y] in ans and (x != position[0] or y != position[1]):\n",
    "                ans.append([x,y])\n",
    "            for d in diraction:\n",
    "                if (x + d[0] >= 0 and x + d[0] < n) and (y + d[1] >= 0 and y + d[1] < m):\n",
    "                    curr = v + terrain[x][y] - terrain[x + d[0]][y + d[1]] - obstacle[x + d[0]][y + d[1]]\n",
    "                    if [x + d[0], y + d[1], curr] in visit:\n",
    "                        continue\n",
    "                    # if visit[x + d[0]][y + d[1]] == 0:\n",
    "                        # visit[x + d[0]][y + d[1]] = 1\n",
    "                    dfs(x + d[0], y + d[1], curr)\n",
    "                        # if v == 1 and (x != position[0] or y != position[1]):\n",
    "                        #     visit[x + d[0]][y + d[1]] = 1\n",
    "                        #     ans.append([x,y])\n",
    "                        # else:\n",
    "                    # visit[x + d[0]][y + d[1]] = 0\n",
    "            \n",
    "                # ans = list(map(list, set(map(tuple, ans))))\n",
    "            # visit[x][y] = 0\n",
    "        ans = list()\n",
    "        dfs(position[0], position[1], 1)\n",
    "        ans.sort()\n",
    "        # ans = list(map(list, set(map(tuple, ans))))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(terrain),len(terrain[0])\n",
    "        sx,sy = position\n",
    "        res = []\n",
    "        speed_rec = [[set() for _ in range(n)] for _ in range(m)]\n",
    "        speed_rec[sx][sy].add(1)\n",
    "        \n",
    "        def dfs(x,y,speed):\n",
    "            for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                if 0<=nx<m and 0<=ny<n:\n",
    "                    new_speed = speed+(terrain[x][y]-terrain[nx][ny]-obstacle[nx][ny])\n",
    "                    if new_speed>0 and new_speed not in speed_rec[nx][ny]:\n",
    "                        if new_speed == 1 and (nx!=sx or ny!=sy):\n",
    "                            res.append([nx,ny])\n",
    "                        speed_rec[nx][ny].add(new_speed)\n",
    "                        dfs(nx,ny,new_speed)\n",
    "            pass\n",
    "\n",
    "        dfs(sx,sy,1)\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(terrain),len(terrain[0])\n",
    "        sx,sy = position\n",
    "        res = []\n",
    "        speed_rec = [[set() for _ in range(n)] for _ in range(m)]\n",
    "        speed_rec[sx][sy].add(1)\n",
    "        \n",
    "        # 每个位置都要用set记录之前所有来到这个位置的速度，不要重复状态\n",
    "        def dfs(x,y,speed):\n",
    "            for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                if 0<=nx<m and 0<=ny<n:\n",
    "                    new_speed = speed+(terrain[x][y]-terrain[nx][ny]-obstacle[nx][ny])\n",
    "                    if new_speed>0 and new_speed not in speed_rec[nx][ny]:\n",
    "                        if new_speed == 1 and (nx!=sx or ny!=sy):\n",
    "                            res.append([nx,ny])\n",
    "                        speed_rec[nx][ny].add(new_speed)\n",
    "                        dfs(nx,ny,new_speed)\n",
    "            pass\n",
    "\n",
    "        dfs(sx,sy,1)\n",
    "        res.sort()\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
